package com.wang.sort2;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author: along
 * @Create: 2021/4/18 17:15
 * @Description:二叉树的序列化和反序列化
 */
public class Demo12_SerializeAndRebuildTree {
//采用什么方式序列化，就采用什么方式反序列化
        public static class Node {
            public int value;
            public Node left;
            public Node right;

            public Node(int data) {
                this.value = data;
            }
        }
        //先序序列化
        public static Queue<String> preSerial(Node head) {
            Queue<String> ans = new LinkedList<>();
            pres(head, ans);
            return ans;
        }

        public static void pres(Node head, Queue<String> ans) {
            if (head == null) {
                ans.add(null);
            } else {
                ans.add(String.valueOf(head.value));
                pres(head.left, ans);
                pres(head.right, ans);
            }
        }
        //后序序列化
        public static Queue<String> poeSerial(Node head) {
            Queue<String> ans = new LinkedList<>();
            pos(head, ans);
            return ans;
        }
        public static void pos(Node head, Queue<String> ans) {
            if (head == null) {
                ans.add(null);
            } else {
                pos(head.left, ans);
                pos(head.right, ans);
                ans.add(String.valueOf(head.value));
            }
        }
        //先序重建
        public static Node buildByPreQueue(Queue<String> prelist) {
            if (prelist == null || prelist.size() == 0) {
                return null;
            }
            return preb(prelist);
        }

        public static Node preb(Queue<String> prelist) {
            String value = prelist.poll();
            if (value == null) {
                return null;
            }
            Node head = new Node(Integer.valueOf(value));
            head.left = preb(prelist);
            head.right = preb(prelist);
            return head;
        }
        //层次序列化
        public static Queue<String> levelSerial(Node head) {
            Queue<String> ans = new LinkedList<>();
            if (head == null) {
                ans.add(null);
            } else {
                ans.add(String.valueOf(head.value));
                Queue<Node> queue = new LinkedList<Node>();
                queue.add(head);
                while (!queue.isEmpty()) {
                    head = queue.poll();
                    if (head.left != null) {
                        ans.add(String.valueOf(head.left.value));
                        queue.add(head.left);
                    } else {
                        ans.add(null);
                    }
                    if (head.right != null) {
                        ans.add(String.valueOf(head.right.value));
                        queue.add(head.right);
                    } else {
                        ans.add(null);
                    }
                }
            }
            return ans;
        }
        //按层次重建
        public static Node buildByLevelQueue(Queue<String> levelList) {
            if (levelList == null || levelList.size() == 0) {
                return null;
            }
            Node head = generateNode(levelList.poll());
            Queue<Node> queue = new LinkedList<Node>();
            if (head != null) {
                queue.add(head);
            }
            Node node = null;
            while (!queue.isEmpty()) {
                node = queue.poll();
                node.left = generateNode(levelList.poll());
                node.right = generateNode(levelList.poll());
                if (node.left != null) {
                    queue.add(node.left);
                }
                if (node.right != null) {
                    queue.add(node.right);
                }
            }
            return head;
        }

        public static Node generateNode(String val) {
            if (val == null) {
                return null;
            }
            return new Node(Integer.valueOf(val));
        }

        // for test
        public static Node generateRandomBST(int maxLevel, int maxValue) {
            return generate(1, maxLevel, maxValue);
        }

        // for test
        public static Node generate(int level, int maxLevel, int maxValue) {
            if (level > maxLevel || Math.random() < 0.5) {
                return null;
            }
            Node head = new Node((int) (Math.random() * maxValue));
            head.left = generate(level + 1, maxLevel, maxValue);
            head.right = generate(level + 1, maxLevel, maxValue);
            return head;
        }

        // for test
        public static boolean isSameValueStructure(Node head1, Node head2) {
            if (head1 == null && head2 != null) {
                return false;
            }
            if (head1 != null && head2 == null) {
                return false;
            }
            if (head1 == null && head2 == null) {
                return true;
            }
            if (head1.value != head2.value) {
                return false;
            }
            return isSameValueStructure(head1.left, head2.left) && isSameValueStructure(head1.right, head2.right);
        }

        public static void main(String[] args) {
            int maxLevel = 5;
            int maxValue = 100;
            int testTimes = 1000000;
            for (int i = 0; i < testTimes; i++) {
                Node head = generateRandomBST(maxLevel, maxValue);
                Queue<String> pre = preSerial(head);
                Queue<String> level = levelSerial(head);
                Node preBuild = buildByPreQueue(pre);
                Node levelBuild = buildByLevelQueue(level);
                if (!isSameValueStructure(preBuild, levelBuild)) {
                    System.out.println("Oops!");
                }
            }
            System.out.println("finish!");
        }
}
